<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 异或，最基础的解法
        var singleNonDuplicate = function (nums) {
            let res = nums[0];
            for (let i = 1; i < nums.length; i++) {
                res ^= nums[i]
            }
            return res
        };
    </script>
    <script>
        // 宫水三叶题解
        // 这题有点脑筋急转弯
        // 由于给定数组有序 且 常规元素总是两两出现，因此如果不考虑“特殊”的单一元素的话，我们有结论：成对元素中的第一个所对应的下标必然是偶数，成对元素中的第二个所对应的下标必然是奇数。
        // https://leetcode-cn.com/problems/single-element-in-a-sorted-array/solution/gong-shui-san-xie-er-duan-xing-fen-xi-yu-17nv/
        var singleNonDuplicate1 = function (nums) {
            // 定义双指针
            let i = 0, j = nums.length - 1;
            while (i < j) {
                let mid = (i + j) >> 1;
                if (mid % 2 == 0) {
                    if (nums[mid] == nums[mid + 1]) {
                        i = mid + 1;
                    } else {
                        j = mid;
                    }
                } else {
                    if (nums[mid] == nums[mid - 1]) {
                        i = mid + 1;
                    } else {
                        j = mid;
                    }
                }
            }
            return nums[i];
        };
        singleNonDuplicate1([1, 1, 2, 3, 3, 4, 4, 8, 8]);
        singleNonDuplicate1([1, 1, 4, 4, 5, 5, 6, 8, 8]);
    </script>
</body>

</html>